The present invention relates generally to computing systems, and more particularly, to techniques for allocation and garbage collection of objects of an object-oriented programming language.
From a computer programming perspective, data which is no longer needed by a computer program can be referred to as “garbage.” In the past, programmers had to write programs that explicitly requested allocation of data and then returned it to the system (e.g., operating system) when it was no longer needed. As such, programs that neglected to return unused storage could have been shut down by the operating system.
Today, some programming languages, such as LISP, and Java™ programming languages, provide a “garbage collector” that frees programmers from concerns about explicitly freeing memory. A garbage collector is useful because it cleans up the memory space by identifying objects that are no longer needed. The memory space can be reclaimed for a more meaningful use. In programming languages such as Java™, a portion of memory is provided as a “heap” for allocation and storage of objects. In a heap, some objects become garbage shortly after their creation, some survive for a long time and then become garbage, and others can remain alive for the entire duration of the program.
A variety of garbage collection schemes can be used to free the memory (e.g., heap) from objects that are no longer used (i.e., have become garbage). Some garbage collection schemes use a “generational” garbage collector. A generational garbage collector divides memory (e.g., a heap) into multiple generations. Typically, the heap is divided into a Young Generation and one or more Older Generations. Objects are initially allocated in the Young Generation. If an object in the Young Generation meets some “promotion” criteria, such as having survived a certain number of collections, then the object is “promoted” to the next generation, namely, an Older Generation, and possibly promoted to the next Older Generation, and so on.
Generally, a generational collector is free to use a different collection strategy for different generations and perform garbage collection on each of the generations separately. Typically, most garbage is collected from the Young Generation. Hence, the garbage collection strategy used in the Young Generation can have a significant amount of influence on overall system performance.
A generational garbage collection scheme is an effective strategy, especially for computing environments that operate with a relatively limited processing power and/or memory (e.g., embedded, handheld, or mobile devices, virtual machine used for smaller devices, etc.). Conventional generational garbage collectors promote all objects in the Young Generation in accordance with a single promotion policy. A single promotion policy, however, typically results in prematurely promoting some objects to the next generation. In other words, some objects are promoted to the next generation even though they become garbage after they have been moved to the next generation.
Accordingly, improved garbage collection strategies are needed.